「提高 - 84」割点和桥

给出无向连通图 $G=(V, E)$：

桥

若对于 $e \in E$，从图中删去边 $e$ 之后，$G$ 分裂为两个不相连的子图，则称 $e$ 为 $G$ 的桥或者割边。

割点

若对于 $v \in E$，从图中删去节点 $x$ 以及所有与 $x$ 关联的边之后，$G$ 分裂成两个或两个以上不相连的子图，则称 $x$ 为 $G$ 的割点。

下面的图中，哪些边是桥，哪些点是割点呢？

通过观察，我们可以看到若图为一棵树，那么每条边都是割边，每个非叶子的节点和儿子节点不只一个的根节点都是割点。

搜索树

在无向连通图中，从任意一个节点出发进行深度优先遍历，每个点只访问一次，所有发生递归的边构成了一棵树，我们称其为“图的搜索树”。如果图不连通的话，那么得到的为每一个连通块的搜索树组成的“搜索树森林”。

树边和回边

对于无向连通图来说，所有的非树边一定连接的是节点和其祖先节点。这样的边称为“回边“。

下图给出了一张无向连通图的搜索树的树边（红色）和回边（绿色）。

时间戳

在执行深度优先遍历的过程中，按照每个节点第一次被访问的顺序，依次将 $N$ 个节点用 $1 \sim N$ 的整数标记，该标记称为 ”时间戳“，一般用数组 $dfn[]$ (Discovery Time)记录该值。

追溯值

为了分析删掉一条边或者一个点以后，图是否依然保持连通，我们引入追溯值的概念。

设 subtree(x) 表示搜索树中以 $x$ 为根的子树。low[x]（Low Link Value）定义为以下节点的时间戳的最小值。

1. subtree(x) 中的节点。
2. 通过 1 条不在搜索树的边，能够到达 subtree(x) 的节点。

追溯值求解过程

在 DFS 遍历过程中，当访问到点 $x$ 的时候。

1. 执行操作 low[x] = dfn[x]
2. 枚举 $x$ 的出边 $(x, y)$。
   • 若 $y$ 未曾访问过，递归访问 $y$，结束以后利用 $low[x] = min(low[x], low[y])$ 更新 $x$ 的追溯值，这是因为 $y$ 能访问到的点 $x$ 也可以访问到。
   • 若 $y$ 曾经访问过，且边 $(x, y)$ 不是 $x$ 的父边，$x$ 可直接回到时间戳更小的节点 $y$，故可通过 $low[x] = min(low[x], dfn[y])$ 更新 $x$ 的追溯值。

情况1，$x$ 的儿子节点 $y$ 可以不经过其父边到达更早访问过的节点。

情况2，$x$ 本身 可以不经过其父边到达更早访问过的节点。

这是红色文字

割边判定法则

无向边 $(x, y)$ 是桥，当且仅当 $(x, y)$ 是搜索树上的边且满足 $dfn[x] < low[y]$。

证明

1. $(x, y)$ 是桥，说明删掉边 $(x, y)$ 以后，$y$ 不再与 $x$ 所在的连通块连通，这意味着 $(x, y)$ 是树边，且 $y$ 无法通过其他边到达 $x$ 或者 $x$ 的祖先，所以有 $dfn[x] < low[y]$。

2. $dfn[x] < low[y]$，说明不经过 $y$ 的父边，$y$ 无法到达 $x$ 或 $x$ 的祖先节点，那么删掉边 $(x, y)$ 之后，$y$ 将不再与 $x$ 所在的连通块连通，所以 $(x, y)$ 是桥。

tip

我们在枚举 $x$ 的出边 $(x, y)$的时候，一定要保证 $(x, y)$ 不是 $x$ 的父边，否则会错误的更新 $x$ 的 low 值。 如上图，如果我们在递归到 $x$ 的时候，错误的利用 $y$ 的 dfn 值将 $x$ 的 low 值更新为了 $2$。那么，当回溯到节点 $y$ 的时候，会发现不满足 dfn[y] < low[x]，从而认为边 $(y, x)$ 不是割边。

无向图求割边参考代码

const int SIZE = 100010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE], n, m, tot, num;
bool bridge[SIZE * 2];

void add(int x, int y) {
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}

void tarjan(int x, int in_edge) {
    dfn[x] = low[x] = ++num;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y, i);
            low[x] = min(low[x], low[y]);

            if (low[y] > dfn[x])
                bridge[i] = bridge[i ^ 1] = true;
        }
        else if (i != (in_edge ^ 1))
            low[x] = min(low[x], dfn[y]);
    }
}

int main() {
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }

    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);

    for (int i = 2; i < tot; i += 2)
        if (bridge[i])
            printf("%d %d\n", ver[i ^ 1], ver[i]);
}

割点判定法则

割点的判定需按照节点是否是根节点分情况讨论。

1. 若 $x$ 不是根节点，则 $x$ 是割点等价于存在 $x$ 的子节点 $y$ 满足 $dfn[x] \le low[y]$。
2. 若 $x$ 是根节点，则 $x$ 是割点等价于 $x$ 的子节点至少有两个。

tip

因为割点判定法则是小于等于号，所以在求割点时，不必考虑父节点和重边的问题，从 $x$ 出发能访问到的所有点的时间戳都可以用来更新 $low[x]$。

上面这段话来自算法进阶指南，我理解的是这会使得所有节点的 low 值都会小于等于其父节点的 dfn 值，但因为判断条件是 $dfn[x] \le low[y]$，所以不会影响判断结果。

const int SIZE = 100010;
int head[SIZE], ver[SIZE * 2], Next[SIZE * 2];
int dfn[SIZE], low[SIZE], stack[SIZE];
int n, m, tot, num, root;
bool cut[SIZE];

void add(int x, int y) {
    ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++num;
    int flag = 0;
    for (int i = head[x]; i; i = Next[i]) {
        int y = ver[i];
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                flag++;
                if (x != root || flag > 1) cut[x] = true;
            }
        } else low[x] = min(low[x], dfn[y]);
    }
}

int main() {
    cin >> n >> m;
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        if (x == y) continue;
        add(x, y), add(y, x);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) root = i, tarjan(i);
    for (int i = 1; i <= n; i++)
        if (cut[i]) printf("%d ", i);
    puts("are cut-vertexes");
}